#include <bits/stdc++.h>

using namespace std;

const int maxn=10004;
const int maxm=10004*2;
const int maxs=1<<4;
const int inf=0x3f3f3f3f;

int g[maxn],v[maxm],w[maxm],nxt[maxm];
int f[maxn][maxs*maxs],ans[maxs];
int n;
int q[maxn];bool inq[maxn];
int qf,qr;

inline void addEdge(const int &x,const int &y,const int &z){
    static int en=0;
    v[en]=y;w[en]=z;nxt[en]=g[x];g[x]=en++;
    v[en]=x;w[en]=z;nxt[en]=g[y];g[y]=en++;
}

inline bool update(int &x,const int &y){if(x>y) return x=y,true;return false;}

inline void spfa(const int &s){
    while(qf!=qr){
        const int &cur=q[qf];
        for(int j=g[cur];~j;j=nxt[j]){
            const int &tar=v[j];
            if(update(f[tar][s],f[cur][s]+w[j])&&!inq[tar]){
                q[qr++]=tar;inq[tar]=1;
                if(qr==maxn) qr=0;
            }
        }
        inq[q[qf]]=0;qf++;
        if(qf==maxn) qf=0;
    }
}

inline void steiner(const int &cnt){
    for(int m=0,end=1<<cnt;m<end;m++){
        for(int i=1;i<=n;i++){
            for(int k=m&m-1;k;k=m&k-1) update(f[i][m],f[i][k]+f[i][k^m]);
            if(f[i][m]!=inf){q[qr++]=i; if(qr==maxn) qr=0;}
        }
        spfa(m);
    }
}

template <typename T> inline void read(T &r){
    char c;bool f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') f=1;
    for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
    if(f) r=-r;
}

int main(){
    int m,d;

    read(n);read(m);read(d);
    memset(g,-1,sizeof g);
    while(m--){
        int x,y,z;
        read(x);read(y);read(z);
        addEdge(x,y,z);
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=d;i++){
        f[i][1<<(i-1)]=0;
        f[n-i+1][1<<(i+d-1)]=0;
    }
    steiner(d*2);

    for(int s=1,end=1<<d;s<end;s++){
        int w=0,repr;
        for(int i=0;i<d;i++)
            if(s&(1<<i)) w|=(1<<i)|(1<<i+d),repr=i+1;
        ans[s]=f[repr][w];
        for(int k=s&s-1;k;k=s&k-1) update(ans[s],ans[k]+ans[s^k]);
    }
    printf("%d\n",ans[(1<<d)-1]==inf?-1:ans[(1<<d)-1]);
    return 0;
}
